package allHot100;

/**
 * 283. 移动零
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 *
 *  思路：
 *      1：可以定义一个索引K从0开始，遍历数组，当当前元素不是0的时候，num[k]等于当前元素，然后k++
 *      2：数组遍历完成后，将k后面的元素都设置为0
 */
public class L_283 {

    /**
     * 根据下标索引移动数字
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0){
            return;
        }
        int k = 0;
        // 遍历数组，当当前元素不是0的时候，num[k]等于当前元素，然后k++
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                nums[k] = nums[i];
                k++;
            }
        }
        //补齐剩余元素
        for (int i = k; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 使用双指针思路
     * 快指针指向非0元素，慢指针指向 0元素，然后进行交换
     */
    public void moveZeros2(int[] nums){
        if (nums == null || nums.length == 0){
            return;
        }
        int slow = 0;
        int fast = 0;
        while (fast < nums.length){
            // 如果快指针指向的元素不是0.则与慢指针进行交换
            if (nums[fast] != 0){
                int temp = nums[fast];
                nums[fast] = nums[slow];
                nums[slow] = temp;
                slow++;
            }
            // fast ++ 继续遍历
            fast++;
        }
    }

}
